In networks, path computation includes determining and finding a suitable path for a connection between a source and a destination, subject to one or more constraints. The connection can be a wavelength (Layer 0), Time Division Multiplexing (TDM) (Layer 1), Ethernet/Multiprotocol Label Switching (MPLS) (Layer 2), Internet Protocol (IP) (Layer 3), or a combination thereof. That is, the connection provides data connectivity in the network between the source and destination. The connection can be viewed as a single layer connection, e.g., a packet connection at Layer 2, an OTN connection at Layer 1, a wavelength at Layer 0, etc. Alternatively, the connection can be viewed as spanning multiple Layers, e.g., an OTN connection on a wavelength. In the past, these multiple Layers (Layer 0, 1, 2, and/or 3) were managed independently including path computation. However, networks are evolving to support the management and control of multiple layers (Layer 0, 1, 2, and/or 3) using control planes, Software Defined Networking (SDN), and the like in a single management plane. Disadvantageously, conventional path computation techniques lack support for multiple layer technology path computation. Specifically, next-generation networks expect that connections can be managed, on-demand with abstraction of the underlying layers and hardware using SDN, Network Functions Virtualization (NFV), control planes, etc. Thus, there is a need for path computation techniques operating a multi-layer path calculation.
Three exemplary conventional path computation techniques are Dijkstra's shortest path algorithm, K shortest path algorithm, and the Bellman-Ford algorithm. Again, each of these conventional path computation techniques does not support multi-layer path calculation. Also, these conventional path computation techniques assume every hop or link is ultimately valid, e.g., a certain hop from port X to port Y is possible as a path is explored, but this same hop may not be valid when considered as a part of an end-to-end path, as the hop may to not be acceptable in order to satisfy some constraints or rules. As described herein, the rules are technical limitations, e.g., an end-to-end path may only have some many hops due to optical reach, etc. Constraints are policy or business limitations, e.g., an end-to-end path must have a maximum latency, etc. The conventional path computation techniques are further limited in defining constraints or rules; that is, these techniques work if all constraints or rules can be expressed in terms of a single “cost” factor at each hop. These techniques do not allow more complex constraints or rules, such as multi-hop constraints or rules.
Additionally, K shortest path algorithms do not work in cases where the constraints or rules are more complex in nature. The “K”-value (K is number of shortest paths that should be considered) has to be increased to a higher value in order to find a viable path that meets the constraints or rules. A suitable K value for the given endpoints, constraints or rules cannot be determined ahead of time, resulting in the need to re-run path calculation with higher K values to find an appropriate path.